Skip to main content

Dynamic Programming

A comprehensive guide to dynamic programming algorithms and techniques for Data Structures and Algorithms.

Table of Contents​

  1. Introduction to Dynamic Programming
  2. Core Principles and Patterns
  3. 1D Dynamic Programming
  4. 2D Dynamic Programming
  5. String Dynamic Programming
  6. Tree Dynamic Programming
  7. Advanced DP Patterns
  8. Space Optimization Techniques
  9. DP on Subsequences and Substrings
  10. Game Theory DP
  11. Digit DP
  12. Common Optimization Tricks

Introduction to Dynamic Programming​

Dynamic Programming (DP) is an algorithmic technique for solving optimization problems by breaking them down into simpler subproblems. It is applicable when the subproblems overlap and have optimal substructure.

Core Concepts​

Optimal Substructure: The optimal solution to a problem contains optimal solutions to subproblems.

Overlapping Subproblems: The same subproblems are solved multiple times in a naive recursive approach.

DP Approaches​

  1. Top-Down (Memoization): Solve recursively and cache results
  2. Bottom-Up (Tabulation): Build solution iteratively from base cases

Basic Template​

// Top-Down Memoization
function dpTopDown(params, memo = new Map()) {
    // Base case
    if (baseCondition) return baseValue;

    // Check memo
    const key = createKey(params);
    if (memo.has(key)) return memo.get(key);

    // Recursive relation
    let result = computeFromSubproblems();

    // Store and return
    memo.set(key, result);
    return result;
}

// Bottom-Up Tabulation
function dpBottomUp(params) {
    // Initialize DP table
    const dp = new Array(size).fill(baseValue);

    // Fill base cases
    dp[0] = baseValue;

    // Fill DP table
    for (let i = 1; i < size; i++) {
        dp[i] = computeFromPrevious(dp, i);
    }

    return dp[size - 1];
}

Core Principles and Patterns​

1. Decision Pattern​

When to use: Problems involving choices at each step.

function decisionDP(i, state) {
    if (i === n) return baseCase;

    // Try all possible decisions
    let result = initialValue;
    for (const decision of possibleDecisions) {
        const subResult = decisionDP(i + 1, newState);
        result = optimize(result, subResult + cost);
    }

    return result;
}

2. State Machine Pattern​

When to use: Problems with different states/modes.

function stateMachineDP(i, currentState) {
    if (i === n) return baseCase;

    let result = initialValue;
    for (const nextState of possibleStates) {
        if (canTransition(currentState, nextState)) {
            const subResult = stateMachineDP(i + 1, nextState);
            result = optimize(result, subResult + transitionCost);
        }
    }

    return result;
}

3. Range Pattern​

When to use: Problems on intervals/ranges.

function rangeDP(left, right) {
    if (left >= right) return baseCase;

    let result = initialValue;
    for (let k = left; k < right; k++) {
        const leftResult = rangeDP(left, k);
        const rightResult = rangeDP(k + 1, right);
        result = optimize(result, leftResult + rightResult + mergeCost);
    }

    return result;
}

1D Dynamic Programming​

1. Fibonacci Sequence​

Classic example of overlapping subproblems:

// Top-Down
function fibMemo(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];

    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

// Bottom-Up
function fibTabulation(n) {
    if (n <= 1) return n;

    const dp = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

// Space Optimized
function fibOptimized(n) {
    if (n <= 1) return n;

    let prev2 = 0, prev1 = 1;

    for (let i = 2; i <= n; i++) {
        const curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

Time Complexity: O(n) | Space Complexity: O(1) optimized

2. Climbing Stairs​

function climbStairs(n) {
    if (n <= 2) return n;

    let oneStep = 1, twoStep = 2;

    for (let i = 3; i <= n; i++) {
        const current = oneStep + twoStep;
        oneStep = twoStep;
        twoStep = current;
    }

    return twoStep;
}

3. House Robber​

function rob(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    let prev2 = 0, prev1 = 0;

    for (const num of nums) {
        const current = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

4. House Robber II (Circular)​

function robCircular(nums) {
    if (nums.length === 1) return nums[0];

    const robRange = (start, end) => {
        let prev2 = 0, prev1 = 0;

        for (let i = start; i <= end; i++) {
            const current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    };

    // Either rob houses 0 to n-2 or 1 to n-1
    return Math.max(
        robRange(0, nums.length - 2),
        robRange(1, nums.length - 1)
    );
}

5. Maximum Subarray (Kadane's Algorithm)​

function maxSubArray(nums) {
    let maxSoFar = nums[0];
    let maxEndingHere = nums[0];

    for (let i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

6. Coin Change​

function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

7. Perfect Squares​

function numSquares(n) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }

    return dp[n];
}

💡 Pattern Recognition: Most 1D DP problems involve making decisions at each position based on previous positions.

2D Dynamic Programming​

1. Unique Paths​

function uniquePaths(m, n) {
    const dp = Array(m).fill().map(() => Array(n).fill(1));

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

// Space Optimized
function uniquePathsOptimized(m, n) {
    let dp = new Array(n).fill(1);

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }

    return dp[n - 1];
}

2. Unique Paths II (With Obstacles)​

function uniquePathsWithObstacles(obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;

    if (obstacleGrid[0][0] === 1) return 0;

    const dp = Array(m).fill().map(() => Array(n).fill(0));
    dp[0][0] = 1;

    // Fill first row
    for (let j = 1; j < n; j++) {
        dp[0][j] = obstacleGrid[0][j] === 1 ? 0 : dp[0][j - 1];
    }

    // Fill first column
    for (let i = 1; i < m; i++) {
        dp[i][0] = obstacleGrid[i][0] === 1 ? 0 : dp[i - 1][0];
    }

    // Fill rest of the grid
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }

    return dp[m - 1][n - 1];
}

3. Minimum Path Sum​

function minPathSum(grid) {
    const m = grid.length;
    const n = grid[0].length;

    const dp = Array(m).fill().map(() => Array(n).fill(0));
    dp[0][0] = grid[0][0];

    // Fill first row
    for (let j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    // Fill first column
    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    // Fill rest
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    return dp[m - 1][n - 1];
}

4. Longest Common Subsequence (LCS)​

function longestCommonSubsequence(text1, text2) {
    const m = text1.length;
    const n = text2.length;

    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

5. 0/1 Knapsack​

function knapsack(weights, values, capacity) {
    const n = weights.length;
    const dp = Array(n + 1).fill().map(() => Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                // Take or don't take the item
                dp[i][w] = Math.max(
                    dp[i - 1][w], // Don't take
                    dp[i - 1][w - weights[i - 1]] + values[i - 1] // Take
                );
            } else {
                dp[i][w] = dp[i - 1][w]; // Can't take
            }
        }
    }

    return dp[n][capacity];
}

// Space Optimized
function knapsackOptimized(weights, values, capacity) {
    let dp = new Array(capacity + 1).fill(0);

    for (let i = 0; i < weights.length; i++) {
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }

    return dp[capacity];
}

6. Edit Distance​

function minDistance(word1, word2) {
    const m = word1.length;
    const n = word2.length;

    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    // Base cases
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i - 1][j] + 1,     // Delete
                    dp[i][j - 1] + 1,     // Insert
                    dp[i - 1][j - 1] + 1  // Replace
                );
            }
        }
    }

    return dp[m][n];
}

String Dynamic Programming​

1. Palindromic Substrings​

function countSubstrings(s) {
    const n = s.length;
    let count = 0;

    // dp[i][j] represents if substring from i to j is palindrome
    const dp = Array(n).fill().map(() => Array(n).fill(false));

    // Single characters are palindromes
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
        count++;
    }

    // Check for 2-character palindromes
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            count++;
        }
    }

    // Check for palindromes of length 3 or more
    for (let len = 3; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;

            if (s[i] === s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                count++;
            }
        }
    }

    return count;
}

2. Longest Palindromic Substring​

function longestPalindrome(s) {
    const n = s.length;
    if (n === 0) return "";

    const dp = Array(n).fill().map(() => Array(n).fill(false));
    let start = 0, maxLen = 1;

    // Single characters
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    // Two characters
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            start = i;
            maxLen = 2;
        }
    }

    // Three or more characters
    for (let len = 3; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;

            if (s[i] === s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                if (len > maxLen) {
                    start = i;
                    maxLen = len;
                }
            }
        }
    }

    return s.substring(start, start + maxLen);
}

3. Decode Ways​

function numDecodings(s) {
    if (s[0] === '0') return 0;

    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1; // Empty string
    dp[1] = 1; // First character (non-zero)

    for (let i = 2; i <= n; i++) {
        const oneDigit = parseInt(s[i - 1]);
        const twoDigit = parseInt(s.substring(i - 2, i));

        if (oneDigit >= 1) {
            dp[i] += dp[i - 1];
        }

        if (twoDigit >= 10 && twoDigit <= 26) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}

4. Word Break​

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict);
    const n = s.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true; // Empty string can always be segmented

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordSet.has(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

Tree Dynamic Programming​

1. Binary Tree Maximum Path Sum​

function maxPathSum(root) {
    let maxSum = -Infinity;

    function maxGain(node) {
        if (!node) return 0;

        // Max sum on the left and right sub-trees
        const leftGain = Math.max(maxGain(node.left), 0);
        const rightGain = Math.max(maxGain(node.right), 0);

        // Max path sum including current node
        const currentMax = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, currentMax);

        // Return max gain if continuing path through current node
        return node.val + Math.max(leftGain, rightGain);
    }

    maxGain(root);
    return maxSum;
}

2. House Robber III (Binary Tree)​

function robTree(root) {
    function dfs(node) {
        if (!node) return [0, 0]; // [rob, not_rob]

        const [leftRob, leftNotRob] = dfs(node.left);
        const [rightRob, rightNotRob] = dfs(node.right);

        // If we rob current node, we can't rob children
        const rob = node.val + leftNotRob + rightNotRob;

        // If we don't rob current, we can take max from children
        const notRob = Math.max(leftRob, leftNotRob) + Math.max(rightRob, rightNotRob);

        return [rob, notRob];
    }

    const [rob, notRob] = dfs(root);
    return Math.max(rob, notRob);
}

3. Diameter of Binary Tree​

function diameterOfBinaryTree(root) {
    let diameter = 0;

    function depth(node) {
        if (!node) return 0;

        const leftDepth = depth(node.left);
        const rightDepth = depth(node.right);

        // Update diameter if path through current node is longer
        diameter = Math.max(diameter, leftDepth + rightDepth);

        return Math.max(leftDepth, rightDepth) + 1;
    }

    depth(root);
    return diameter;
}

Advanced DP Patterns​

1. Matrix Chain Multiplication​

function matrixChainOrder(dimensions) {
    const n = dimensions.length - 1; // Number of matrices

    // dp[i][j] = minimum cost to multiply matrices from i to j
    const dp = Array(n).fill().map(() => Array(n).fill(0));

    // l is chain length
    for (let l = 2; l <= n; l++) {
        for (let i = 0; i <= n - l; i++) {
            const j = i + l - 1;
            dp[i][j] = Infinity;

            for (let k = i; k < j; k++) {
                const cost = dp[i][k] + dp[k + 1][j] +
                           dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}

2. Burst Balloons​

function maxCoins(nums) {
    // Add boundary balloons with value 1
    const balloons = [1, ...nums, 1];
    const n = balloons.length;

    // dp[i][j] = max coins from balloons between i and j (exclusive)
    const dp = Array(n).fill().map(() => Array(n).fill(0));

    for (let len = 2; len < n; len++) {
        for (let left = 0; left < n - len; left++) {
            const right = left + len;

            for (let k = left + 1; k < right; k++) {
                const coins = balloons[left] * balloons[k] * balloons[right];
                dp[left][right] = Math.max(
                    dp[left][right],
                    dp[left][k] + dp[k][right] + coins
                );
            }
        }
    }

    return dp[0][n - 1];
}

3. Regular Expression Matching​

function isMatch(s, p) {
    const m = s.length;
    const n = p.length;

    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(false));

    // Base case: empty pattern matches empty string
    dp[0][0] = true;

    // Handle patterns like a*, a*b*, a*b*c*
    for (let j = 2; j <= n; j += 2) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                // Zero occurrences
                dp[i][j] = dp[i][j - 2];

                // One or more occurrences
                if (s[i - 1] === p[j - 2] || p[j - 2] === '.') {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            } else if (s[i - 1] === p[j - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }

    return dp[m][n];
}

4. Wildcard Matching​

function isMatchWildcard(s, p) {
    const m = s.length;
    const n = p.length;

    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(false));

    dp[0][0] = true;

    // Handle patterns starting with *
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } else if (s[i - 1] === p[j - 1] || p[j - 1] === '?') {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }

    return dp[m][n];
}

Space Optimization Techniques​

1. Rolling Array Pattern​

function optimizedDP(input) {
    const n = input.length;

    // Instead of dp[i][j], use current and previous
    let prev = new Array(n).fill(0);
    let curr = new Array(n).fill(0);

    // Initialize base cases
    prev[0] = baseValue;

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < n; j++) {
            curr[j] = computeFromPrevious(prev, j);
        }

        [prev, curr] = [curr, prev]; // Swap arrays
    }

    return prev[n - 1];
}

2. Single Array Optimization​

function singleArrayDP(input) {
    const n = input.length;
    let dp = new Array(n).fill(initialValue);

    // Process in reverse order to avoid overwriting needed values
    for (let i = 0; i < n; i++) {
        for (let j = n - 1; j >= 0; j--) {
            dp[j] = computeNewValue(dp, j);
        }
    }

    return dp[target];
}

DP on Subsequences and Substrings​

1. Longest Increasing Subsequence​

function lengthOfLIS(nums) {
    if (nums.length === 0) return 0;

    const dp = new Array(nums.length).fill(1);

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Math.max(...dp);
}

// Optimized O(n log n) solution
function lengthOfLISOptimized(nums) {
    const tails = [];

    for (const num of nums) {
        let left = 0, right = tails.length;

        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        if (left === tails.length) {
            tails.push(num);
        } else {
            tails[left] = num;
        }
    }

    return tails.length;
}

2. Longest Common Substring​

function longestCommonSubstring(text1, text2) {
    const m = text1.length;
    const n = text2.length;

    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    let maxLength = 0;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
    }

    return maxLength;
}

3. Count Distinct Subsequences​

function numDistinct(s, t) {
    const m = s.length;
    const n = t.length;

    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    // Empty string t can be formed from any string in one way
    for (let i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // Don't use current character from s
            dp[i][j] = dp[i - 1][j];

            // Use current character if it matches
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }

    return dp[m][n];
}

4. Palindromic Subsequences​

function countPalindromicSubsequences(s) {
    const n = s.length;
    const MOD = 1000000007;

    // dp[i][j] = number of distinct palindromic subsequences in s[i:j+1]
    const dp = Array(n).fill().map(() => Array(n).fill(0));

    // Single characters
    for (let i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;

            if (s[i] === s[j]) {
                dp[i][j] = (2 * dp[i + 1][j - 1]) % MOD;

                // Find first and last occurrence of s[i] in s[i+1:j]
                let left = i + 1, right = j - 1;
                while (left <= right && s[left] !== s[i]) left++;
                while (left <= right && s[right] !== s[i]) right--;

                if (left > right) {
                    dp[i][j] = (dp[i][j] + 2) % MOD;
                } else if (left === right) {
                    dp[i][j] = (dp[i][j] + 1) % MOD;
                } else {
                    dp[i][j] = (dp[i][j] - dp[left + 1][right - 1] + MOD) % MOD;
                }
            } else {
                dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + MOD) % MOD;
            }
        }
    }

    return dp[0][n - 1];
}

Game Theory DP​

1. Stone Game​

function stoneGame(piles) {
    const n = piles.length;

    // dp[i][j] = max difference (first player - second player)
    // when playing optimally on piles[i:j+1]
    const dp = Array(n).fill().map(() => Array(n).fill(0));

    // Base case: single pile
    for (let i = 0; i < n; i++) {
        dp[i][i] = piles[i];
    }

    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;

            // Take left pile or right pile
            dp[i][j] = Math.max(
                piles[i] - dp[i + 1][j],  // Take left
                piles[j] - dp[i][j - 1]   // Take right
            );
        }
    }

    return dp[0][n - 1] > 0;
}

2. Predict the Winner​

function PredictTheWinner(nums) {
    const n = nums.length;
    const dp = Array(n).fill().map(() => Array(n).fill(0));

    // Base case
    for (let i = 0; i < n; i++) {
        dp[i][i] = nums[i];
    }

    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            dp[i][j] = Math.max(
                nums[i] - dp[i + 1][j],
                nums[j] - dp[i][j - 1]
            );
        }
    }

    return dp[0][n - 1] >= 0;
}

3. Nim Game​

function canWinNim(n) {
    // If n is divisible by 4, first player loses
    return n % 4 !== 0;
}

// For more complex Nim variants
function nimGame(piles) {
    let xor = 0;
    for (const pile of piles) {
        xor ^= pile;
    }
    return xor !== 0; // First player wins if XOR is non-zero
}

Digit DP​

1. Count Numbers with Digit Sum​

function countNumbersWithSum(n, targetSum) {
    const str = n.toString();
    const len = str.length;

    // Memoization: [position][sum][tight][started]
    const memo = new Map();

    function dp(pos, sum, tight, started) {
        if (pos === len) {
            return started && sum === targetSum ? 1 : 0;
        }

        const key = `${pos}-${sum}-${tight}-${started}`;
        if (memo.has(key)) return memo.get(key);

        let result = 0;
        const limit = tight ? parseInt(str[pos]) : 9;

        for (let digit = 0; digit <= limit; digit++) {
            const newSum = sum + digit;
            const newTight = tight && (digit === limit);
            const newStarted = started || (digit > 0);

            if (!newStarted || newSum <= targetSum) {
                result += dp(pos + 1, newSum, newTight, newStarted);
            }
        }

        memo.set(key, result);
        return result;
    }

    return dp(0, 0, true, false);
}

2. Numbers At Most N Given Digit Set​

function atMostNGivenDigitSet(digits, n) {
    const nStr = n.toString();
    const len = nStr.length;
    const digitSet = new Set(digits);

    // Count numbers with fewer digits
    let result = 0;
    for (let i = 1; i < len; i++) {
        result += Math.pow(digits.length, i);
    }

    // Count numbers with same number of digits
    for (let i = 0; i < len; i++) {
        const currentDigit = nStr[i];
        let count = 0;

        for (const digit of digits) {
            if (digit < currentDigit) {
                count++;
            }
        }

        result += count * Math.pow(digits.length, len - i - 1);

        if (!digitSet.has(currentDigit)) {
            break;
        }

        if (i === len - 1) {
            result++; // The number n itself
        }
    }

    return result;
}

Common Optimization Tricks​

1. State Compression​

// Use bitmask to represent states
function tsp(graph) {
    const n = graph.length;
    const memo = new Map();

    function dp(mask, pos) {
        if (mask === (1 << n) - 1) {
            return graph[pos][0]; // Return to start
        }

        const key = `${mask}-${pos}`;
        if (memo.has(key)) return memo.get(key);

        let result = Infinity;
        for (let city = 0; city < n; city++) {
            if ((mask & (1 << city)) === 0) {
                const newMask = mask | (1 << city);
                result = Math.min(result, graph[pos][city] + dp(newMask, city));
            }
        }

        memo.set(key, result);
        return result;
    }

    return dp(1, 0); // Start from city 0
}

2. Coordinate Compression​

function compressCoordinates(points) {
    const xCoords = [...new Set(points.map(p => p[0]))].sort((a, b) => a - b);
    const yCoords = [...new Set(points.map(p => p[1]))].sort((a, b) => a - b);

    const xMap = new Map();
    const yMap = new Map();

    xCoords.forEach((x, i) => xMap.set(x, i));
    yCoords.forEach((y, i) => yMap.set(y, i));

    return points.map(([x, y]) => [xMap.get(x), yMap.get(y)]);
}

3. Monotonic Queue Optimization​

function maxSlidingWindow(nums, k) {
    const result = [];
    const deque = []; // Store indices

    for (let i = 0; i < nums.length; i++) {
        // Remove elements outside window
        while (deque.length && deque[0] <= i - k) {
            deque.shift();
        }

        // Remove smaller elements
        while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }

        deque.push(i);

        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

4. Convex Hull Trick​

// For problems with recurrence: dp[i] = min(dp[j] + cost(j, i))
class ConvexHullTrick {
    constructor() {
        this.lines = []; // [slope, intercept, index]
    }

    addLine(slope, intercept, index) {
        const newLine = [slope, intercept, index];

        // Remove lines that become irrelevant
        while (this.lines.length >= 2) {
            const [s1, b1] = this.lines[this.lines.length - 2];
            const [s2, b2] = this.lines[this.lines.length - 1];
            const [s3, b3] = newLine;

            // Check if middle line is redundant
            if ((b3 - b1) * (s1 - s2) >= (b2 - b1) * (s1 - s3)) {
                this.lines.pop();
            } else {
                break;
            }
        }

        this.lines.push(newLine);
    }

    query(x) {
        let left = 0, right = this.lines.length - 1;

        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            const val1 = this.lines[mid][0] * x + this.lines[mid][1];
            const val2 = this.lines[mid + 1][0] * x + this.lines[mid + 1][1];

            if (val1 <= val2) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return [this.lines[left][0] * x + this.lines[left][1], this.lines[left][2]];
    }
}

Problem-Solving Strategy​

1. Identify DP Problems​

Signs that a problem might use DP:

  • Optimization problems (min/max)
  • Counting problems
  • Decision problems (yes/no)
  • Problems with overlapping subproblems
  • Problems with optimal substructure

2. DP Development Process​

  1. Define the state: What parameters uniquely identify a subproblem?
  2. Write the recurrence relation: How does the current state relate to previous states?
  3. Identify base cases: What are the simplest subproblems?
  4. Implement: Choose between top-down (memoization) or bottom-up (tabulation)
  5. Optimize: Can you reduce space complexity?

3. Common Pitfalls​

  • Incorrect state definition: Make sure your state captures all necessary information
  • Wrong base cases: Double-check your base cases
  • Off-by-one errors: Be careful with array indices
  • Overflow issues: Use appropriate data types and modular arithmetic when needed
  • Time/space complexity: Consider if your solution is efficient enough

4. Testing Strategy​

function testDP(dpFunction, testCases) {
    for (const [input, expected] of testCases) {
        const result = dpFunction(...input);
        console.log(`Input: ${JSON.stringify(input)}`);
        console.log(`Expected: ${expected}, Got: ${result}`);
        console.log(`✅ ${result === expected ? 'PASS' : 'FAIL'}\n`);
    }
}

// Example usage
const fibTestCases = [
    [[0], 0],
    [[1], 1],
    [[5], 5],
    [[10], 55]
];

testDP(fibOptimized, fibTestCases);

Conclusion​

Dynamic Programming is a powerful technique that can solve complex problems efficiently by breaking them down into simpler subproblems. The key to mastering DP is:

  1. Practice pattern recognition - Learn to identify when DP is applicable
  2. Master state definition - The most crucial step in DP problem solving
  3. Understand space-time tradeoffs - When to use memoization vs tabulation
  4. Learn optimization techniques - Space optimization, monotonic queues, convex hull tricks
  5. Build intuition through practice - Solve problems across different categories

Remember: DP problems often have multiple valid approaches. Focus on correctness first, then optimize for time and space complexity.

💡 Pro Tip: When stuck on a DP problem, try working backwards from the desired result to understand what information you need to track in your state.